from collections import defaultdict


class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        memory = defaultdict(bool)

        def is_scramble(i, j, n):
            if n == 1:
                result = s1[i] == s2[j]
                return result

            if n == 2:
                a, b, c, d = s1[i], s1[i+1], s2[j], s2[j+1]
                result = (a == c and b == d or a == d and b == c)
                return result

            if (i, j, n) in memory:
                return memory[(i, j, n)]

            for m in range(1, n):
                if is_scramble(i, j, m) and is_scramble(i + m, j + m, n - m):
                    memory[(i, j, n)] = True
                    return True
            for m in range(1, n):
                if is_scramble(i, j + n - m, m) and is_scramble(i + m, j, n - m):
                    memory[(i, j, n)] = True
                    return True
            memory[(i, j, n)] = False
            return False

        return is_scramble(0, 0, len(s1))


s1 = "great"
s2 = "rgeat"
print(Solution().isScramble(s1, s2))
